POI working up | FFY's Blog

题意

有两个人和一个$n \times m$的矩阵,一个从左上角出发,只能向右,向下走,去右下角;另一个从右上角出发只能向左,向下走,去左下角.矩阵的每一格有一个权值,走过会得到这个权值.很显然,两个人肯定会相遇,他们相遇的那一格的权值不取,求两人只相遇一次权值和的最大值

题解

读完题,你是否有想到方格取数
做法非常简单也非常暴力,开四个二维数组分别记录从四个角出发的最优解,然后$n^2$枚举合法的点,更新$ans$
因为只相遇一次,所以两人相遇时只有两种直线走法,不会转弯

• 注意下标,容易迷糊
• 记得开long long

  Coding:

  1#include<cstdio>
  2#include<cstring>
  3#include<algorithm>
  4#define ll long long
  5using namespace std;
  6const int maxn=1010;
  7ll mp[maxn][maxn],f1[maxn][maxn];
  8ll f2[maxn][maxn],f3[maxn][maxn];
  9ll f4[maxn][maxn];
  10int n,m;
  11int main()
  12{
  13  scanf("%d%d",&amp;n,&amp;m);
  14  for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lld",&amp;mp[i][j]);
  15  for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
  16  f1[i][j]=max(f1[i-1][j],f1[i][j-1])+mp[i][j];
  17  for(int i=n;i;i--)for(int j=m;j;j--)
  18  f2[i][j]=max(f2[i+1][j],f2[i][j+1])+mp[i][j];
  19  for(int i=1;i<=n;i++)for(int j=m;j;j--)
  20  f3[i][j]=max(f3[i-1][j],f3[i][j+1])+mp[i][j];
  21  for(int i=n;i;i--)for(int j=1;j<=m;j++)
  22  f4[i][j]=max(f4[i+1][j],f4[i][j-1])+mp[i][j];
  23  //暴力美学
  24  ll ans=0;
  25  for(int i=2;i<n;i++)for(int j=2;j<m;j++)
  26  {
  27      ans=max(ans,f1[i][j-1]+f2[i][j+1]+f3[i-1][j]+f4[i+1][j]);
  28      ans=max(ans,f1[i-1][j]+f2[i+1][j]+f3[i][j+1]+f4[i][j-1]);
  29  }
  30  printf("%lld\n",ans);
  31  return 0;
  32}